
/**
 * @author LKQ
 * @date 2022/2/21 22:46
 * @description chaur
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode root = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
        solution.insertionSortList(root);
    }
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(-6000, null);
        ListNode currentNode = head;
        while (currentNode != null) {
            dummy = insert(dummy, new ListNode(currentNode.val));
            currentNode = currentNode.next;
        }
        return dummy.next;
    }
    public ListNode insert(ListNode head, ListNode insertNode) {
        ListNode dummy = new ListNode(-6000, head);
        ListNode pre = head;
        while (head != null) {
            if (insertNode.val > head.val && head.next == null) {
                head.next = insertNode;
                break;
            }else if (insertNode.val > head.val) {
                pre = head;
                head = head.next;
            }else {
                pre.next = insertNode;
                insertNode.next = head;
                break;
            }
        }
        return dummy.next;
    }
}
